Sobre les gramàtiques regulars
Una gramàtica incontextual G=(V,\Sigma,P,S) se’n diu lineal per la dreta si totes les seves produccions són de la forma A \to wB o A \to w, on A, B \in V i w \in \Sigma^*. En el cas en què totes les produccions de G són de la forma A \to Bw o A \to w, es diu que G és lineal per l’esquerra. Una gramàtica incontextual és regular si és lineal per la dreta o lineal per l’esquerra. Una gramàtica incontextual és lineal si conté produccions de la forma A \to wB, A \to Bw o A \to w.
Forma normal. Demostreu que per a tota gramàtica lineal per la dreta G=(V,\Sigma,P,S) existeix una gramàtica equivalent en què totes les produccions són de la forma A \to aB o A \to \lambda, on A, B \in V i a \in \Sigma. Observeu que es pot aplicar una transformació simètrica a les gramàtiques lineals per l’esquerra.
Gramàtiques lineals. Demostreu que una gramàtica lineal pot generar un llenguatge no regular.
Gramàtiques regulars. Demostreu que la classe de llenguatges generats per gramàtiques regulars coincideix amb la dels regulars.
ConsellDemostreu-ho només per les gramàtiques lineals per la dreta o per l’esquerra (es pot fer independentment per totes dues i són simètriques). Feu servir la forma normal del primer punt.
Inambigüitat dels regulars. Demostreu que tots els llenguatges regulars són inambigus.
ConsellFeu servir la construcció (del punt anterior) per transformar un autòmat determinista en una gramàtica regular i demostreu que la gramàtica obtinguda és inambigua.